#include<iostream>
#include<vector>
#include<string>

//面试题01.01.字符串中唯一的字符
bool isUnique(string astr){
    //鸽巢原理优化
    if(astr.length()>26){
        return false;
    }

    //位图思想
    int bitmap = 0;

    for(auto ch : astr){
        //先求出字符所对应的位置下标
        int i = ch - 'a';

        //如果当前字符的位置为一说明字符重复
        if((bitmap>>i)&1==1){
            return false;
        }
        bitmap |= (1 << i);
    }

    return true;
} 

//268.丢失的数字
int missingNumber(vector<int>& nums){
    //位运算
    int ans = nums[0];
    for (int i = 1; i < nums.size();i++){
        ans ^= nums[i];
    }
    for (int i = 0; i < nums.size() + 1;i++){
        ans ^= i;
    }
    return ans;
}

//371.两整数之和
int getSum(int a, int b){
    while(b){
        int cur=a;
        a ^= b;
        b &= cur;
        b <<= 1;
    }
    return a;
}

//LCR.004.只出现一次的数字
int singleNumber(vector<int>& nums){
    int ret = 0;
    for (int i = 0; i < 32;i++){
        int sum = 0;
        //求出数组中每个数的第i位之和
        for(auto num : nums){
            if((num>>i)&1==1){
                sum++;
            }
        }

        //求出只出现一次数字的第i位是1还是0
        sum %= 3;
        //修改ret的第i位
        if(sum==1){
            ret |= (1 << i);
        }
    }
    return ret;
}

//面试题17.19消失的两个数字
vector<int> missingTwo(vector<int>& nums){
    //1.将当前数组和没有消失的两个数字的原数组全部异或
    int tmp = 0;
    for (auto num : nums){
        tmp ^= num;
    }
    for (int i = 1; i <= nums.size() + 2;i++){
        tmp ^= i;
    }

    //2.找到异或后的值哪一位为1
    int mapbit = 0;
    for (int i = 0;i<32;i++){
        if(((tmp>>i)&1)==1){
            mapbit = i;
            break;
        }
    }

    //3.根据异或后的值哪一位为1将两个数组中的所有值划分成两个，两个消失的数字分别在其中一个
    int ans1 = 0, ans2 = 0;
    for (auto num : nums){
        if(((num>>mapbit)&1)==1){
            ans1 ^= num;
        }
        else{
            ans2 ^= num;
        }
    }
    for (int i = 1; i <= nums.size() + 2; i++)
    {
        if(((i>>mapbit)&1)==1){
            ans1 ^= i;
        }
        else{
            ans2 ^= i;
        }
    }

    return {ans1, ans2};
}

int main(){

    return 0;
}